package liecai_class.day04;

import java.util.Arrays;

public class MyHashMap <K,V> {
    private Entry<K,V> [] tables = null;
    private int initialCapacity;
    private float loadFactor;
    private int size;

    public MyHashMap() {
        this(16);
    }

    public MyHashMap(int initialCapacity) {
        this(initialCapacity,0.75f);
    }

    public MyHashMap(int initialCapacity, float loadFactor) {
        this.initialCapacity = initialCapacity;
        this.loadFactor = loadFactor;
        size = 0;
        tables = new Entry[initialCapacity];
    }

    /**
     * 获取桶编号
     */
    private int bIndex(K k){
        return Math.abs(k.hashCode()) % initialCapacity;
    }
    private int bIndex(Entry<K,V> entry){
        K k = entry.getK();
        return bIndex(k);
    }

    /**
     * 判断键是否存在
     */
    public boolean contains(K k){
        //计算桶的编号
        int bIndex = bIndex(k);
        //如果桶中有数据，检查桶中是否有Entry的key为k
        if(tables[bIndex] != null){
            for(Entry<K,V> entry : tables[bIndex]){
                if(entry.getK() == k || entry.getK().equals(k)){
                    //找到返回true
                    return true;
                }
            }
        }
        //桶中没有数据，或有数据但没有Entry的key是k，返回false
        return false;
    }

    /**
     * 写入数据
     */
    public V put(K k,V v){
        //创建Entry,保存数据
        Entry<K,V> entry = new Entry<K,V>(k,v,null);
        //计算桶编号
        int bIndex = bIndex(entry);
        //如果已经有数据，处理数据覆盖的问题
        if(tables[bIndex] != null) {
            //遍历已有数据，如果有重复的键，覆盖
            for(Entry<K,V> nextEntry : tables[bIndex]){
                if(nextEntry.getK() == k || nextEntry.getK().equals(k)){
                    nextEntry.setV(v);
                    //返回存储的值
                    return v;
                }
            }
        }
        //加入链表，头插
        entry.setNext(tables[bIndex]);
        tables[bIndex] = entry;
        //size加1
        size++;

        //处理扩容机制
        if(size >= initialCapacity * loadFactor){
            //原有的数据
            Entry<K,V> [] oldTables = tables;
            //扩容
            initialCapacity = initialCapacity * 2;
            tables = new Entry[initialCapacity];
            size = 0;
            //遍历旧数据，写入新tables
            for(Entry<K,V> kvEntry : oldTables){
                if(kvEntry!=null){
                    for(Entry<K,V> entry1 : kvEntry){
                        put(entry1.getK(),entry1.getV());
                    }
                }
            }
        }

        //返回存储的值
        return v;
    }

    /**
     * 获取数据
     */
    public V get(K k){
        //计算桶的编号
        int bIndex = bIndex(k);
        //如果桶中有数据，检查桶中是否有Entry的key为k
        if(tables[bIndex] != null){
            for(Entry<K,V> entry : tables[bIndex]){
                if(entry.getK() == k || entry.getK().equals(k)){
                    //找到返回其值
                    return entry.getV();
                }
            }
        }
        //桶中没有数据，或有数据但没有Entry的key是k，返回null
        return null;
    }

    /**
     * 移除数据
     */
    public V remove(K k){
        //计算桶的编号
        int bIndex = bIndex(k);
        //如果桶中有数据，检查桶中是否有Entry的key为k
        if(tables[bIndex] != null){
            Entry<K,V> preEntry = null;
            for(Entry<K,V> entry : tables[bIndex]){
                //找到Entry的key为k，则移除该Entry
                if(entry.getK() == k || entry.getK().equals(k)){
                    if(preEntry == null){
                        //头结点，头移除
                        tables[bIndex] = entry.getNext();
                        entry.setNext(null);
                    }else{
                        //非头结点，中间移除
                        preEntry.setNext(entry.getNext());
                        entry.setNext(null);
                    }
                    //size数量-1
                    size--;
                    //找到返回其值
                    return entry.getV();
                }
                preEntry = entry;
            }
        }
        //桶中没有数据，或有数据但没有Entry的key是k，返回null
        return null;
    }

    /**
     * 清空Map
     */
    public void clear(){
        initialCapacity = 16;
        loadFactor = 0.75f;
        size = 0;
        tables = new Entry[initialCapacity];
    }

    @Override
    public String toString() {
        return "MyHashMap{" +
                "tables=" + Arrays.toString(tables) +
                ", bsize=" + initialCapacity +
                ", size=" + size +
                '}';
    }
}
